1. Field Of The Invention
The present invention relates to the field of multicomputer systems having a plurality of nodes (i.e. processors with independent memories) arranged in a network. Specifically, the present invention relates to the control of application programs executing in a multicomputer system.
2. Prior Art
Many task scheduling systems exist in the prior art. Most of these prior art task schedulers exist within operating systems designed for single processor computer systems or multiprocessor systems where the processors share memory. Task schedulers manage the execution of independent tasks in support of application programs executing in the computer system. Application programs (hereinafter applications) comprise processing logic for performing a specific function for a computer user or for the manipulation of a specific type of data. Applications are typically distinguished from operating system software of which a task scheduler is a part. Task schedulers are used mainly to optimize the allocation of available processor execution time across a plurality of prioritized tasks. In this manner, a single processor may be used to execute a plurality of different tasks.
Recently, shared memory computer system architectures have evolved into multicomputer architectures. Multicomputer systems typically comprise a two or three dimensional array (mesh) of independent processors having independent memories, wherein each processor is capable of executing different instruction streams simultaneously. Although multicomputer systems provide a greatly increased capacity for processing throughput, scheduling tasks in multicomputer systems greatly increases in complexity. In order to deal with this complexity, some prior art multicomputer task scheduling systems impose severe processing constraints. For example, some prior art multicomputer task schedulers allow only a single application program to be executed at a time. By imposing this constraint, a problem is eliminated wherein a task of a first application program is indefinitely suspended while tasks of a second application are executing. A significant disadvantage of this prior art approach, however, is that additional applications must be queued for execution until the currently executing application has terminated. Queuing applications for execution is a significant drawback because any single application may execute for an indeterminate length of time (i.e. hours or days).
Other prior art multicomputer task schedulers impose a restriction of limiting any single application to execution by a predetermined subset of the available processors. The multicomputer is thereby divided into a plurality of physical partitions of processors. A single application is restricted to execution only within a single partition. Similarly, each physical partition may only have a single application executing on processors within the partition. This partitioning scheme typically reflects the physical attributes of the multicomputer interconnection scheme such as sub-cubes of a hyper-cube or rectangles of a mesh of processors. This method forces a particular processor or node to belong to only one partition. Although this prior art method of physical partitioning allows a small number of applications to execute at once in a multicomputer, a number of disadvantages also exist. The main disadvantage with this method is the inability to optimally predetermine the necessary size of a partition for a particular application. In practice, a multicomputer system may be used to execute a number of various applications. Some computation intensive applications may benefit from the allocation of many processors for use by the application. On the other hand, other applications may require relatively few processing resources. Because of these processing dynamics, the physical pre-allocation of a set of processors for any particular application is unlikely to yield the appropriate level of computing resources for a particular application. A second disadvantage of the prior art method of physical partitioning is an implicit restriction imposed on the number of applications which can be executed concurrently on the multicomputer system. Because processors of a multicomputer system are solely allocated to a particular application, it will be apparent that the multicomputer system may only execute a number of applications corresponding to the number of partitions available.
Thus, a better task scheduling system is needed for multicomputer systems.